from __future__ import division
import re, porter, stemming, unicodedata, shlex, sys, time
from math import sqrt
from collections import deque
from itertools import imap, chain
from operator import mul
from itertools import izip 

STOPWORDS = frozenset(('a','about','an','are','as','at','be','but','by','for','from','has','have','he','his','in','is','it','its',
            'more','new','of','on','one','said','say','that','the','their','they','this','to','was','which','who','will','with','you'))

ps = stemming.PorterStemmer()

if sys.platform == 'win32':
    now = time.clock
else:
    now = time.time
    
def tostr(s):
    if type(s)==unicode:
        return s.encode('utf8','ignore')
    else:
        return s

def tostr1(s):
    if type(s)==unicode:
        return unicodedata.normalize('NFKD', s).encode('ascii','ignore')
    else:
        return s

def stradv(s):
    if not s: return s
    else:
        t = list(s)
        t[-1] = chr(ord(s[-1])+1)
        return ''.join(t)

def distance(s, t):
    """Returns the Levenshtein edit distance between two strings."""
    m, n = len(s), len(t)
    d = [range(n+1)]
    d.extend([[i] for i in range(1,m+1)])
    for i in range(m):
        for j in range(n):
            d[i+1].append(min(d[i][j+1]+1,  # deletion
                              d[i+1][j]+1,  # insertion
                              d[i][j]+1-int(s[i]==t[j])) # substitution
                         )
    return d[m][n]

def dotproduct(a, b):
    return sum(imap(mul, a, b))

def flatten(listOfLists):
    return list(chain.from_iterable(listOfLists))

def stem(word, fast=1):
    if fast:
        return porter.stem(word)
    else:
        return ps.stem(word)

def buildSkipPoint(id):
    '''Build skip points for input postings. if length of id is P,
    use sqrt(P) evenly-spaced skip pointers.
    @param id: input posting, a list of document id
    @return: a dict of skip points (input's index)
    input list:[2,4,8,16,19,23,28,43]
    output skip points:{0:3,3:7}'''
    skippoint = {}
    #index increment
    l = len(list(id))
    dx = int(l//sqrt(l))+1
    i = 0
    while(i < l):
        if i+dx < l:
            skippoint[i] = i+dx
        i += dx
    return skippoint

def isAdjacent(postings, idxs):
    for i in xrange(1,len(idxs)):
        if postings[i][idxs[i]] - postings[i-1][idxs[i-1]] != 1:
            return False
    return True
    
def containOp(line):
    '''check whether input query line contain operator
    @param line: the input string
    @return: return True if line contains operator, otherwise return False'''
    # consider query "AND OR NOT" as a phrase query
    if line.find('"')>-1:
        return False 
    elif line.find('OR')>-1:     
        return True
    elif line.find('NOT')>-1:
        return True
    elif line.find('AND')>-1:
        return True
    return False

def getPrecedence(operator):
    '''Get precedence of each operator: brackets have highest precedence, and OR has lowest precedence
    @param operator: operator string
    @return: precedence of operator'''
    precedence = {'AND':2, 'OR':1, 'NOT':3, '(':0, ')':4}
    if operator in precedence:
        return precedence[operator]
    else:
        return None

def strSplit(line):
    '''Split a string by space
    @param line: the input string
    @return: an array of substrings or None if line can't be splitted'''
    if line.find(' ')>-1:
        return line.split(' ')
    else:
        return None
    
def infix2postfix(s):
    def isOperand(ss):
        if ss in ['(',')','AND','OR','NOT']:
            return False
        else:
            return True
    postfix = deque()
    temp = deque()
    wildcard_mask = '_wildcard_'
    infix = shlex.shlex(s.replace('*',wildcard_mask))
    for i in infix :
        i = i.replace(wildcard_mask,'*')
        if i == '(':
            temp.append(i)
        elif i == ')':
            next = temp.pop()
            while next != '(':
                postfix.append(next)
                next = temp.pop()
        elif isOperand(i):
            postfix.append(i)
        else:
            p = getPrecedence(i)
            while len(temp) != 0 and p <= getPrecedence(temp[-1]):
                postfix.append(temp.pop())
            temp.append(i)
    while temp:
        postfix.append(temp.pop())
    return postfix

def argmax(score):
    return max(izip(score.values(), score.keys()))[1]

def mean(list):
    sum = 0.0
    for value in list:
        sum += value
    return (sum/len(list))